package util

import "fmt"

type Node[T any] struct {
	key  T
	val  T
	next *Node[T]
	prev *Node[T]
}

type LRUCache struct {
	cap  int
	data *map[string]*Node[string]
	head *Node[string]
	tail *Node[string]
}

func Constructor(capacity int) LRUCache {
	if capacity < 0 {
		capacity = 0
	}
	data := make(map[string]*Node[string], capacity)
	head := Node[string]{}
	return LRUCache{
		cap:  capacity,
		data: &data,
		head: &head,
		tail: nil,
	}
}

func (this *LRUCache) Get(key string) string {
	if node, ok := (*this.data)[key]; ok {
		this.renew(node)
		return node.val
	}
	return ""
}

func (this *LRUCache) debug() {
	fmt.Println("--------")
	head := this.head
	for head.next != nil {
		fmt.Printf("data: %d %d\n", head.next.key, head.next.val)
		head = head.next
	}
	if this.tail != nil {
		fmt.Println("tail", this.tail.key, this.tail.val)
	}
	fmt.Println("--------")
}

func (this *LRUCache) Put(key string, value string) {
	if node, ok := (*this.data)[key]; ok {
		node.val = value
		this.renew(node)
	} else {
		node := Node[string]{
			key:  key,
			val:  value,
			next: this.head.next,
			prev: this.head,
		}
		if node.next != nil {
			node.next.prev = &node
		}
		if this.head.next != nil {
			this.head.next.prev = &node
		}
		this.head.next = &node
		(*this.data)[key] = &node
		//fmt.Println("put", key, value)
		if len(*this.data) > this.cap {
			//fmt.Println("len(*this.data)", len(*this.data))
			delete(*this.data, this.tail.key)
			if this.tail == nil {
				panic("BUG")
			}
			if this.tail.prev == this.head {
				this.tail = nil
			} else {
				this.tail = this.tail.prev
				this.tail.next = nil
			}
		} else if node.next == nil {
			this.tail = &node
		}
	}
}

func (this *LRUCache) renew(node *Node[string]) {
	if this.head.next == node && node.next == nil {
		return
	}
	if node.next == nil {
		this.tail = node.prev
	}
	node.prev.next = node.next
	if node.next != nil {
		node.next.prev = node.prev
	}
	node.next = this.head.next
	node.prev = this.head
	if this.head.next != nil {
		this.head.next.prev = node
	}
	this.head.next = node
}

func (this *LRUCache) Delete(key string) {
	if node, ok := (*this.data)[key]; ok {
		// 如果删除的是尾节点
		if this.tail == node {
			this.tail = node.prev
		}
		// 如果删除的是头节点
		if this.head.next == node {
			this.head.next = node.next
		} else {
			node.prev.next = node.next
		}
		if node.next != nil {
			node.next.prev = node.prev
		}
		delete(*this.data, key)
	}
}
